#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>
#include <gmp.h>
#include <time.h>

#define POWER_32 4294967296LLU

#define POWER_16 65536

void Multiply16(unsigned short int *x, unsigned short int *y,
		unsigned short int *z, size_t sx, size_t sy, size_t *sz) {
	unsigned short int carry;
	unsigned int p;

	int var;
	for (var = 0; var < (sx+sy); ++var) {
		z[var] = 0;
	}

	int i, j;
	for (i = 0; i < sx; ++i) {
		carry = 0;
		//no need to run the following loop if x[i]=0
		for (j = 0; j < sy; ++j) {
			p = x[i] * y[j]+ z[i+j]+ carry;
			z[i+j] = (u_int16_t)(p & 0xffff);
			carry = p>>16;
		}
		z[i+sy] = carry;
	}
	if (carry=0) {
		*sz = i+j;
	} else {
		*sz = i+sy;
	}
}
